package aloge;

import java.util.Arrays;

/**
 * 计数排序
 */
public class CountingSort {

    /**
     * nums必须大于等于0
     *
     * @param nums 数据
     * @param max 最大值
     * @return 排好序的
     */
    public int[] countingSort(int[] nums, int max) {
        int[] counting = new int[max + 1];
        for (int num : nums) {
            counting[num] = counting[num] + 1;
        }
        for (int i = 1; i <= max; i++) {
            counting[i] = counting[i -1] + counting[i];
        }
        int[] sortedNums = new int[nums.length];
        for (int num : nums) {
            sortedNums[counting[num] - 1] = num;
            counting[num] = counting[num] - 1;
        }
        return sortedNums;
    }

    public static void main(String[] args) {
        CountingSort countingSort = new CountingSort();
        int[] ints = countingSort.countingSort(new int[]{1, 2, 3, 5, 2, 3, 3, 3, 4}, 5);
        System.out.println(Arrays.toString(ints));
    }

}
